//面试题 02.07. 链表相交
//思路：1.先让长的一个链表走到与短链表长度一致的位置
//2.curA = curB，这里等于是内存是一块的，不是值相等。找到就返回curA
//3.while完都没找到一致的，就返回NULL
#include <stdio.h>
struct ListNode {
	int val;
	struct ListNode* next;
};
//法一：
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//	struct ListNode* curA = headA, * curB = headB;
//	int lena = 0, lenb = 0, i = 0;
//
//	while (curA)
//	{
//		lena++;
//		curA = curA->next;
//	}
//	while (curB)
//	{
//		lenb++;
//		curB = curB->next;
//	}
//
//	curA = headA, curB = headB;
//	while (curA && curB)//存在任一为空就跳出
//	{
//		if (lena > lenb)
//		{
//			while (i < lena - lenb)
//			{
//				curA = curA->next;
//				i++;
//			}
//		}
//		else
//		{
//			while (i < lenb - lena)
//			{
//				curB = curB->next;
//				i++;
//			}
//		}
//		//判断
//		if (curA == curB)
//			return curA;
//		//迭代
//		curA = curA->next;
//		curB = curB->next;
//	}
//	return NULL;
//}

//法二：优于法一在长链表先走差步时不冗余
struct ListNode* getIntersectionNode(struct ListNode* headA,
    struct ListNode* headB) {
    struct ListNode* curA = headA, * curB = headB;
    int lena = 0, lenb = 0, i = 0;

    while (curA)
    {
        lena++;
        curA = curA->next;
    }
    while (curB)
    {
        lenb++;
        curB = curB->next;
    }

    //长的先走差步
    int gap = abs(lena - lenb);
    struct ListNode* longList = headA, * shortList = headB;
    if (lena < lenb)
    {
        longList = headB, shortList = headA;
    }
    while (gap--)
    {
        longList = longList->next;
    }

    while (longList && shortList)
    {
        //判断
        if (longList == shortList)
            return longList;
        //迭代
        longList = longList->next;
        shortList = shortList->next;
    }
    return NULL;
}